import java.util.Scanner;

@SuppressWarnings({"all"})
public class Bank {
    //声明并初始化部分变量
    static int[] available = {10, 5, 7}; // available表示还有多少可用资源
    static int[][] max = {{7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 0, 3}};// Max表示各进程对资源的最大需求数
    static int[][] allocation = {{0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}};// 表示已分配的资源矩阵
    static int[][] need;// need矩阵表示各进程最多还需要多少资源
    static int[] request; // request表示进程此次申请的各种资源数
    static int[] sequence_safe; // 安全序列数组
    static int process_nums; // 定义进程的数量
    static int resource_nums; // 定义资源的种类数量
    static boolean flag; // 定义标志变量
    static int[] work;//进程可用的资源数
    static int[][] works;//用于打印每个进程的work信息
    static boolean[] finish;

    //资源初始化
    static void init() {
        // 输入进程数
        Scanner in = new Scanner(System.in);
        /*
         * 先不用调用in.close()方法关闭，在main函数中我们还需要 输入，如果这时候关闭了在运行时会报错（不能找到元素） Exception in
         * thread "main" java.util.NoSuchElementException
         */
        process_nums = 5;
        resource_nums = 3;
        // 初始化数组
        request = new int[resource_nums]; // request的长度等于资源种类，某个进程分别申请的各个资源个数
        sequence_safe = new int[process_nums];//安全序列数组长度等于进程数
        need = new int[process_nums][resource_nums];
        //计算余下资源数
        for (int j = 0; j < process_nums; j++) {
            for (int i = 0; i < resource_nums; i++) {
                available[i] = available[i] - allocation[j][i];
            }
        }
        // 计算需求矩阵
        for (int i = 0; i < process_nums; i++) {
            for (int j = 0; j < resource_nums; j++) {
                need[i][j] = max[i][j] - allocation[i][j];//需求每个进程的需求等于最大-已分配
            }
        }
    }

    //查看当状态表
    static void show(int select) {
        if (select == 1) {
            System.out.println("状态表：");
            System.out.println("Process\t\t|Max\t\t|Allocation\t|Need\t\t|Available\t|");
            for (int i = 0; i < process_nums; i++) {
                System.out.print(i + "                ");
                for (int m = 0; m < resource_nums; m++) System.out.print(max[i][m] + "  ");//max
                System.out.print("        ");
                for (int m = 0; m < resource_nums; m++) System.out.print(allocation[i][m] + "  ");//allocation
                System.out.print("        ");
                for (int m = 0; m < resource_nums; m++) System.out.print(need[i][m] + "  ");//need
                System.out.print("        ");
                for (int m = 0; m < resource_nums; m++) {
                    if (i == 0) {
                        System.out.print(available[m] + "   ");
                    }
                }
                System.out.println();
            }
        } else {
            System.out.println("安全序列表：");
            System.out.println("Process\t\t|Work\t\t|Need\t\t|Allocation\t|Work+Allocation\t|Finish");
            for (int temp : sequence_safe) {
                System.out.print(temp + "                ");
                for (int m = 0; m < resource_nums; m++) System.out.print(works[temp][m] + "  ");//max
                System.out.print("        ");
                for (int m = 0; m < resource_nums; m++) System.out.print(need[temp][m] + "  ");//need
                System.out.print("        ");
                for (int m = 0; m < resource_nums; m++) System.out.print(allocation[temp][m] + "  ");//allocation
                System.out.print("        ");
                for (int m = 0; m < resource_nums; m++)
                    System.out.print(allocation[temp][m] + works[temp][m] + "  ");//max
                System.out.print("             " + finish[temp] + "  ");
                System.out.print("        ");
                System.out.println();
            }
        }
    }

    //将work与need比较
    // 当m中的全部元素分别大于或等于n中的全部元素的时候返回true，否则返回false
    static boolean compare(int[] m, int[] n) {
        for (int i = 0; i < resource_nums; i++) {
            if (m[i] < n[i])
                return false;
        }
        return true;
    }

    //求安全序列
    static boolean safe() {
        works = new int[process_nums][resource_nums];
        work = new int[resource_nums];
        finish = new boolean[process_nums];
        sequence_safe = new int[process_nums];
        int num = 0; // 已分配进程的个数
        int l = 0;
        // 定义一个work数组来存储available，因为work中途会发生变化，不确定是否为最终结果
        for (int i = 0; i < resource_nums; i++) {
            work[i] = available[i];
            works[0][i] = available[i];
        }
        for (int i = 0; i < process_nums; i++) {
            finish[i] = false;
        }
        /* 核心算法有多少个进程就循环多少次，每次循环遍历need一次，若满足条件，释放资源后num+1 */
        for (int i = 0; i < process_nums; i++) {
            if (num == process_nums) break;// 若进程已全部加入分配完成
            for (int j = 0; j < process_nums; j++) {
                if (finish[j]) {//若该进程已经完成则跳过这个进程
                    continue;
                } else {
                    if (compare(work, need[j])) {//将work即可用的资源与该进程的need比较，work大于即可进入分配
                        finish[j] = true; // 将进程j标记为已分配
                        // 将进程j加入安全序列
                        sequence_safe[l++] = j;
                        num++;
                        // 释放进程资源
                        for (int e = 0; e < 3; e++) {
                            works[j][e] = work[e];//把当前的word记录到words
                        }
                        for (int k = 0; k < resource_nums; k++) {
                            work[k] = work[k] + allocation[j][k];
                        }
                    }
                }
            }
        }
        //查看是否有进程为false有则不安全
        for (int i = 0; i < process_nums; i++) {
            if (!finish[i])
                return false;
        }
        show(2);
        // 输出安全序列
        System.out.print("安全序列为：");
        for (int i = 0; i < process_nums; i++) {
            System.out.print(sequence_safe[i] + " ");
        }
        System.out.println();
        return true;
    }

    //资源请求
    // 申请资源之后的检测
    static void resafe(int n) {// n为请求资源的进程编号3+
        if (compare(available, request) && compare(request, need[n])) {
            for (int i = 0; i < resource_nums; i++) { // 试分配资源
                allocation[n][i] = allocation[n][i] + request[i];
                need[n][i] = need[n][i] - request[i];
                available[i] = available[i] - request[i];
            }
            // 判断是否处于安全状态
            if (safe()) {
                System.out.println("允许进程" + n + "申请资源！");
            } else {
                System.out.println("处于非安全状态，不允许进程" + n + "申请资源！");
                for (int i = 0; i < resource_nums; i++) { // 把试分配资源回收
                    allocation[n][i] = allocation[n][i] - request[i];
                    need[n][i] = need[n][i] + request[i];
                    available[i] = available[i] + request[i];
                }
            }
        } else {
            System.out.println("申请资源越界！");
            return;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n; // 进程编号
        init();
        show(1);
        if (safe()) {
            System.out.println("存在安全序列，初始状态安全！");
        } else
            System.out.println("不存在安全序列，初始状态不安全！");

        System.out.print("请输入请求资源的进程号：");
        n = in.nextInt();
        System.out.println("请输入三类资源的数量");
        for (int i = 0; i < resource_nums; i++) {
            request[i] = in.nextInt();
        }
        resafe(n);
    }
}
 
 